/*
给你二叉树的根节点 root 和一个整数目标和 targetSum，
找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
*/
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    void dfs(TreeNode* root, vector<vector<int>>& res, vector<int>& path, int targetSum) {
        if (root == nullptr) {
            return;
        }

        path.push_back(root->val);
        targetSum -= root->val;

        // 达到一个叶子节点
        if (root->left == nullptr && root->right == nullptr) {
            if (targetSum == 0) {
                res.push_back(path);
            }
        }

        dfs(root->left, res, path, targetSum);
        dfs(root->right, res, path, targetSum);
        // 弹出一个，这样本次深度搜索不会影响下次搜索的结果
        // 注意只需弹出一次，因为在本地递归中，也只push了一次
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        vector<int> path;

        dfs(root, res, path, targetSum);

        return res;
    }
};